#include <stack>
#include <vector>

using namespace std;

//非递归
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
};

class Solution
{
public:
    vector<int> postorderTraversal(TreeNode *root)
    {
        stack<TreeNode *> st;
        vector<int> ret;
        TreeNode *cur = root;
        TreeNode *pre = nullptr;
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode *top = st.top();

            if (top->right == nullptr || top->right == pre)
            {
                ret.push_back(top->val);
                st.pop();
                pre = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return ret;
    }
};